Segment routing (SR) leverages the source routing and tunneling paradigms to steer a packet through a set of segments. SR can be directly applied to the multi-protocol label switching (MPLS) data plane with no change to the forwarding plane. However, MPLS data planes have equal cost multi-path (ECMP) load balancing defined by Entropy labels. Applying Entropy labels, however, causes some issues.
FIG. 1 illustrates a segment-routed network example. The ingress label switched router (LSR) (I) wants to send traffic to egress LSR (E). In this example, the traffic is required to go through nodes S1 and S2. This requirement could be due to traffic engineering or to apply services at those nodes. This traffic should get the benefits of ECMP as it transits the network from I to S1, S1 to S2 and S2 to E. P is representative of an LSR in the transit network. In this example, L-S1, L-S2 and L-E denote the node Segment Identifiers (node-SID) of LSRs 51, S2 and E respectively. To benefit from ECMP, entropy labels should be used. Two possible ways to use the entropy labels and their associated problems are discussed below.
In this option a single entropy label is used for all segments. The ingress LSR encodes the entropy label (EL) below all the SIDs. Thus the label stack would look like <L-S1, L-S2, L-E, ELI, EL> <remaining packet header>. RFC 6790 describes a label stack. RFC 6790 requires that the label immediately preceding an EL in the MPLS label stack be an Entropy Label Identifier (ELI). A primary disadvantage of this approach is that as the label stack grows due to an increase in the number of SIDs, the EL goes deeper in the label stack. As a result, intermediate LSRs (such as P) have to walk the label stack at least until the EL to perform correct multipath load balancing decisions and have to access a larger number of bytes in the packet header. As an example if the packet is required to go through 10 specific LSRs, then the label stack is 12 (10 SIDs+ELI+EL) labels deep and the intermediate LSR has to access 48 bytes of memory to process each packet. However intermediate LSRs are built for high speed e.g. 100G/400G/1T line rates and it becomes significantly expensive to access memory at those processing speeds.
In the second option, an EL is used per segment. The ingress LSR pushes an <ELI, EL> before pushing a SID when ECMP is required to reach the LSR of that SID. In this example, for FIG. 1, the ingress LSR encoded label stack would look like <L-S1, ELI, EL1, L-S2, ELI, EL2, L-E, ELI, EL3> where all the ELs would typically have the same value. A primary disadvantage of this approach is that the size of the label stack grows significantly, almost 3 times as the number of SIDs in the label stack. In the same example as above if the packet is required to go through 10 specific LSRs, then the label stack is 30 (10 SIDs, 10 ELIs, 10 ELs) labels deep, i.e, 120 bytes of just packet header. This overhead is quite high where bandwidth is scarce and especially where actual user-payload is small. In a network such as the Radio Access Network (RAN) or Mobile Backhaul Network (MBH) these are typical characteristics and can lead to significant inefficiency.
Therefore, there is a need in the art to solve the above described problems in order to reduce the inefficiencies present in using entropy labels for segment routing.